package com.acwing.lc.part1;

import java.util.ArrayList;
import java.util.List;

/**
 * @author rkc
 * @date 2022/9/11 10:40
 */
public class LC29两数相除 {

    public int divide(int x, int y) {
        List<Long> ls = new ArrayList<>();
        boolean minus = (x < 0 && y > 0) || (x > 0 && y < 0);
        long a = Math.abs((long) x), b = Math.abs((long) y);
        //倍增，预处理 b * 2 ^ i
        for (long i = b; i <= a; i = i + i) ls.add(i);
        long ans = 0;
        for (int i = ls.size() - 1; i >= 0; i--) {
            if (a >= ls.get(i)) {
                a -= ls.get(i);
                ans += 1L << i;
            }
        }
        if (minus) ans = -ans;
        if (ans > Integer.MAX_VALUE || ans < Integer.MIN_VALUE) return Integer.MAX_VALUE;
        return (int) ans;
    }
}
